|
In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corresponding vertices lie within a unit distance of each other. They are commonly formed from a Poisson point process, making them a simple example of a random structure. ==Characterizations== There are several possible definitions of the unit disk graph, equivalent to each other up to a choice of scale factor: * A graph formed from a collection of points in the Euclidean plane, in which two points are connected if their distance is below a fixed threshold. * An intersection graph of equal-radius circles, or of equal-radius disks (see Fig. 1). * A graph formed from a collection of equal-radius circles, in which two circles are connected by an edge if one circle contains the centre of the other circle. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「unit disk graph」の詳細全文を読む スポンサード リンク
|